NP-complétude du problème du flowshop à deux machines avec des opérations couplées
Identifieur interne : 000206 ( Main/Exploration ); précédent : 000205; suivant : 000207NP-complétude du problème du flowshop à deux machines avec des opérations couplées
Auteurs : Nadjat Meziani [Algérie] ; Ammar Oulamara ; Mourad Boudhar [Algérie]Source :
Descripteurs français
- mix :
Abstract
Dans ce travail, Nous considérons le problème du flowshop à deux machines avec des opérations couplées.
Chaque tâche est composée de deux opérations couplées sur la première machine séparées par un délai exact et d'une seule opération sur la deuxième machine. L'objectif est de minimiser le makespan. Nous étudions la complexité d'un sous problème et nous montrons qu'il est NP-difficile. Pour la résolution du problème général, nous proposons des heuristiques avec des expérimentations numériques et nous présentons des sous problèmes polynomiaux.
Chaque tâche est composée de deux opérations couplées sur la première machine séparées par un délai exact et d'une seule opération sur la deuxième machine. L'objectif est de minimiser le makespan. Nous étudions la complexité d'un sous problème et nous montrons qu'il est NP-difficile. Pour la résolution du problème général, nous proposons des heuristiques avec des expérimentations numériques et nous présentons des sous problèmes polynomiaux.
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 006209
- to stream Hal, to step Curation: 006209
- to stream Hal, to step Checkpoint: 000177
- to stream Main, to step Merge: 000206
- to stream Main, to step Curation: 000206
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr">NP-complétude du problème du flowshop à deux machines avec des opérations couplées</title><author><name sortKey="Meziani, Nadjat" sort="Meziani, Nadjat" uniqKey="Meziani N" first="Nadjat" last="Meziani">Nadjat Meziani</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-446631" status="INCOMING"><orgName>Université Abderrahmane Mira Béjaia</orgName><desc><address><country key="DZ"></country></address></desc><listRelation><relation active="#struct-446628" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-446628" type="direct"><org type="institution" xml:id="struct-446628" status="INCOMING"><orgName>Université Abderrahmane Mira Béjaia</orgName></org></tutelle></tutelles></hal:affiliation><country>Algérie</country></affiliation></author><author><name sortKey="Oulamara, Ammar" sort="Oulamara, Ammar" uniqKey="Oulamara A" first="Ammar" last="Oulamara">Ammar Oulamara</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-446632" status="INCOMING"><orgName>LORIA - UMR 7503,Campus Scientifique - BP 239, 54506 Vandoeuvre-les-Nancy Cedex, France</orgName><listRelation><relation active="#struct-446629" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-446629" type="direct"><org type="institution" xml:id="struct-446629" status="INCOMING"><orgName>Laboratoire LORIA</orgName></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Boudhar, Mourad" sort="Boudhar, Mourad" uniqKey="Boudhar M" first="Mourad" last="Boudhar">Mourad Boudhar</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-446633" status="INCOMING"><orgName>Laboratoire RECITS, Faculté de Mathématiques,USTHB, BP 32, Bab-Ezzouar, El-Alia 16111, Alger, Algérie</orgName><desc><address><country key="DZ"></country></address></desc><listRelation><relation active="#struct-446630" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-446630" type="direct"><org type="institution" xml:id="struct-446630" status="INCOMING"><orgName>Laboratoire RECITS, Faculté de Mathématiques,USTHB, BP 32, Bab-Ezzouar, El-Alia 16111, Alger, Algérie</orgName></org></tutelle></tutelles></hal:affiliation><country>Algérie</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01260752</idno><idno type="halId">hal-01260752</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-01260752</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-01260752</idno><date when="2015-12-02">2015-12-02</date><idno type="wicri:Area/Hal/Corpus">006209</idno><idno type="wicri:Area/Hal/Curation">006209</idno><idno type="wicri:Area/Hal/Checkpoint">000177</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000177</idno><idno type="wicri:Area/Main/Merge">000206</idno><idno type="wicri:Area/Main/Curation">000206</idno><idno type="wicri:Area/Main/Exploration">000206</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="fr">NP-complétude du problème du flowshop à deux machines avec des opérations couplées</title><author><name sortKey="Meziani, Nadjat" sort="Meziani, Nadjat" uniqKey="Meziani N" first="Nadjat" last="Meziani">Nadjat Meziani</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-446631" status="INCOMING"><orgName>Université Abderrahmane Mira Béjaia</orgName><desc><address><country key="DZ"></country></address></desc><listRelation><relation active="#struct-446628" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-446628" type="direct"><org type="institution" xml:id="struct-446628" status="INCOMING"><orgName>Université Abderrahmane Mira Béjaia</orgName></org></tutelle></tutelles></hal:affiliation><country>Algérie</country></affiliation></author><author><name sortKey="Oulamara, Ammar" sort="Oulamara, Ammar" uniqKey="Oulamara A" first="Ammar" last="Oulamara">Ammar Oulamara</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-446632" status="INCOMING"><orgName>LORIA - UMR 7503,Campus Scientifique - BP 239, 54506 Vandoeuvre-les-Nancy Cedex, France</orgName><listRelation><relation active="#struct-446629" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-446629" type="direct"><org type="institution" xml:id="struct-446629" status="INCOMING"><orgName>Laboratoire LORIA</orgName></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Boudhar, Mourad" sort="Boudhar, Mourad" uniqKey="Boudhar M" first="Mourad" last="Boudhar">Mourad Boudhar</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-446633" status="INCOMING"><orgName>Laboratoire RECITS, Faculté de Mathématiques,USTHB, BP 32, Bab-Ezzouar, El-Alia 16111, Alger, Algérie</orgName><desc><address><country key="DZ"></country></address></desc><listRelation><relation active="#struct-446630" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-446630" type="direct"><org type="institution" xml:id="struct-446630" status="INCOMING"><orgName>Laboratoire RECITS, Faculté de Mathématiques,USTHB, BP 32, Bab-Ezzouar, El-Alia 16111, Alger, Algérie</orgName></org></tutelle></tutelles></hal:affiliation><country>Algérie</country></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term> délai exact </term><term> makespan.</term><term> opérations couplées </term><term>flowshop </term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="fr">Dans ce travail, Nous considérons le problème du flowshop à deux machines avec des opérations couplées.
Chaque tâche est composée de deux opérations couplées sur la première machine séparées par un délai exact et d'une seule opération sur la deuxième machine. L'objectif est de minimiser le makespan. Nous étudions la complexité d'un sous problème et nous montrons qu'il est NP-difficile. Pour la résolution du problème général, nous proposons des heuristiques avec des expérimentations numériques et nous présentons des sous problèmes polynomiaux.</div></front></TEI><affiliations><list><country><li>Algérie</li></country></list><tree><noCountry><name sortKey="Oulamara, Ammar" sort="Oulamara, Ammar" uniqKey="Oulamara A" first="Ammar" last="Oulamara">Ammar Oulamara</name></noCountry><country name="Algérie"><noRegion><name sortKey="Meziani, Nadjat" sort="Meziani, Nadjat" uniqKey="Meziani N" first="Nadjat" last="Meziani">Nadjat Meziani</name></noRegion><name sortKey="Boudhar, Mourad" sort="Boudhar, Mourad" uniqKey="Boudhar M" first="Mourad" last="Boudhar">Mourad Boudhar</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000206 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000206 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-01260752
|texte= NP-complétude du problème du flowshop à deux machines avec des opérations couplées
}}
| This area was generated with Dilib version V0.6.33. |  |